package com.lql.sort;

import java.util.Random;

/**
 * 选择排序
 */
public class SelectSort {
    /*
     * 第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]~arr[n-1]中选取最小值，
     * 与arr[1]交换，第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…，
     * 第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，…,
     * 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，
     * 总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
     * */
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 1, 7};
        int[] ints = new int[80000];
        Random random = new Random();
        for (int i = 0; i < 80000; i++) {
            ints[i] = random.nextInt(80000);
        }
        selectSorted(ints);
    }

    /**
     * 选择排序
     *
     * @param arrays 待排序的数组
     */
    public static int[] selectSorted(int[] arrays) {
        int minIndex;//最小值的下标索引
        int min;//最小值
        long startTime = System.currentTimeMillis();
        System.out.println("开始：" + startTime);
        for (int i = 0; i < arrays.length - 1; i++) {
            //排序次数为数组长度减一次
            //假设第一个数据为最小值
            minIndex = i;
            min = arrays[i];
            //寻找最小值，依次和后面的元素做对比
            for (int j = i + 1; j < arrays.length; j++) {
                if (arrays[j] < min) {
                    //发现更小的值，进行重新赋值
                    min = arrays[j];
                    minIndex = j;
                }
            }
            //交换最小值到当前排序位置
            if (i != minIndex) {
                //当两者不是同一个数时，才发生交换
                arrays[minIndex] = arrays[i];
                arrays[i] = min;
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println("结束：" + endTime);
        float l = (endTime - startTime) / 1000f;
        System.out.println("总时间：" + l + "秒");
        return arrays;
    }
}


